class Solution {
public:
    //https://gitee.com/link?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fsubarray-sums-divisible-by-k%2F
    int subarraysDivByK(vector<int>& nums,int k) 
    {
        int sum = 0;
        int count = 0;
        vector<int> mp(k);//由于该hash中存储的都是sum%k故他大笑设置为k足以
        mp[0] = 1;//0这个数的余数
        for(int i = 0; i < nums.size(); i++)
        {
            sum += nums[i];
            int rem = ((sum % k) + k)%k;//修正sum<0时产生余数<0的情况
            count += mp[rem];
            mp[rem]++;
        }
        return count;
    }

    //https://gitee.com/link?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fcontiguous-array%2F
    int findMaxLength(vector<int>& nums) 
    {
        unordered_map<int, int> u1;
        int sum = 0;
        int len = 0;
        for(int right = 0; right < nums.size(); right++)
        {
            if(nums[right] == 1) sum += 1;
            else sum -= 1;
            if(sum == 0) len = max(len, right + 1);
            else if(u1.count(sum)) len = max(len, right - u1[sum]);
            if(!u1.count(sum)) u1[sum] = right;
        }
        return len;
    }

    //优化版
    int findMaxLength1(vector<int>& nums) 
    {
        unordered_map<int, int> u1;//u1中存储的是和为sum的最左边下标
        int sum = 0;
        int len = 0;
        u1[0] = -1;//倘若sum==0则直接right - (-1) 即可
        for(int right = 0; right < nums.size(); right++)
        {
            if(nums[right] == 1) sum += 1;
            else sum -= 1;
            if(u1.count(sum)) len = max(len, right - u1[sum]);
            else u1[sum] = right;
        }
        return len;
    }

    //https://gitee.com/link?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fmatrix-block-sum%2F
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) 
    {
        int size = mat.size();
        int msize = mat[0].size();
        vector<vector<int>> vv1(size + 1, vector<int>(msize + 1));
        for(int i = 1; i < size + 1; i++)
        {
            for(int f = 1; f < msize + 1; f++)
            {
                vv1[i][f] = vv1[i - 1][f] + vv1[i][f - 1] - vv1[i - 1][f - 1] + mat[i - 1][f - 1];
            }
        }
        vector<vector<int>> vv2(size, vector<int>(msize));
        for(int i = 0; i < size; i++)
        {
            for(int f = 0; f < msize; f++)
            {
                int imin = i - k < 0? 0:i - k;
                int fmin = f - k < 0? 0:f - k;
                int imax = i + k > size - 1? size - 1:i + k;
                int fmax = f + k > msize - 1? msize - 1:f + k;
                vv2[i][f] = vv1[imax + 1][fmax + 1] - vv1[imin][fmax + 1] - vv1[imax + 1][fmin] + vv1[imin][fmin];
            }
        }
        return vv2;
    }
};